
import java.util.*;

/**
 * @author Shezil Kheraj
 * @version 1.0
 */
public class NFAtoDFA {
	private String[][] ret;

	public static void main(String[] args) {
		// String[][] nfa = new String[][]
		// {{"State","a","b","c","E"},{"1","2",null,"4","1"},{"2",null,"3",null,"2,1"},{"3","2",null,null,"3"},{"4",null,null,"3","4,3"}};
		String[][] nfa = new String[][] { { "State", "a", "b", "E" },
				{ "1", "3", null, "2,1" }, { "2", "4,5", null, "2" },
				{ "3", null, "4", "3" }, { "4", "5", "5", "4" },
				{ "5", null, null, "5" } };
		// String[] fState = {"4"};
		HashSet<Integer> fState = new HashSet<Integer>();
		fState.add(2);
		fState.add(4);
		NFAtoDFA newTest = new NFAtoDFA(nfa, fState);
	}

	public NFAtoDFA(String[][] nfa, HashSet<Integer> st) {
		ArrayList<String> acceptStates = new ArrayList<String>();
		for (int i : st) {
			acceptStates.add(Integer.toString(i));
		}
		ret = nfaToDfa(nfa, acceptStates);
	}

	public static String trace(String[][] nfa, String state, int column) {
		for (int j = 1; j < nfa.length; j++) {
			if (state.equals(nfa[j][0])) {
				for (int i = 1; i < nfa[1].length; i++) {
					if (i != nfa[j].length - 1) {
						if (nfa[j][column] == null) {
							return null;
						} else {
							for (int k = 0; k < nfa.length; k++) {
								if (nfa[j][column].equals(nfa[k][0])) {
									if (nfa[k][nfa[k].length - 1] == null) {
										return nfa[k][0];
									} else {
										return nfa[k][nfa[k].length - 1];
									}

								}
							}
						}
					}
				}
			}
		}
		return null; // will never get to this
	}

	public String[][] nfaToDfa(String[][] nfa, ArrayList<String> st) {

		String[][] dfa = new String[nfa.length][nfa[1].length - 1]; // creates a
																	// table of
																	// size 1
																	// less than
																	// that of
																	// nfa in
																	// width
		ArrayList<String> states = new ArrayList<String>();
		String[] var = new String[nfa[1].length];
		ArrayList<String> temp = new ArrayList<String>();
		int stateCounter = 0;
		int currentState = 1;
		String r = "";

		// Set the starting state for the dfa
		if (nfa[1][nfa[1].length - 1] == null) {
			dfa[1][0] = nfa[1][0];
		} else {
			dfa[1][0] = nfa[1][nfa[1].length - 1];
		}

		stateCounter++;

		// stateCounter++;
		// dfa[stateCounter][0] = nfa[currentState][nfa[1].length-1];

		// fills out the first row in dfa
		// for(int i = 1; i < nfa[1].length; i++) {
		// if(i != nfa[1].length -1) {
		// if(nfa[1][i] == null) {
		// dfa[1][i] = null;
		// }
		// else {
		// for (int k = 0; k < nfa.length; k++) {
		// if (nfa[1][i].equals(nfa[k][0])) {
		// if (nfa[k][nfa[k].length-1] == null) {
		// dfa[1][i] = nfa[k][0];
		// }
		// else {
		// dfa[1][i] = nfa[k][nfa[k].length-1];
		// }
		//
		// }
		// }
		// }
		// }
		// }
		//
		// //add the next state(s) on the dfa table
		// for (int i = 1; i < nfa[currentState].length-1; i++) {
		// if(dfa[1][i] != null) {
		// int x = 0;
		// for (int j = 1; j < nfa.length; j++){
		// if (dfa[currentState][i].equals(dfa[j][0])) {
		// x = 1;
		// break;
		// }
		// }
		// if (x == 0){
		// stateCounter++;
		// dfa[stateCounter][0] = dfa[currentState][i];
		// }
		// }
		// }
		// currentState++;

		// more states?
		while (currentState <= stateCounter) {
			String hold = "";
			for (int i = 1; i < nfa[1].length - 1; i++) {
				temp.clear();
				for (int c = 0; c < dfa[currentState][0].length(); c++) {
					if (dfa[currentState][0].charAt(c) == ',') {
						temp.add(hold);
						hold = "";
					} else {
						hold = hold + dfa[currentState][0].charAt(c);
					}
				}
				temp.add(hold);
				hold = "";
				String value = "";

				for (int t = 0; t < temp.size(); t++) {

					String check = "";
					int x = 1;
					check = trace(nfa, temp.get(t), i); // returns the value(s)
														// of the state it goes
														// to with a variable
					if (check != null) {
						if (value.length() > 0) {
							value = value + "," + check;
						} else {
							value = value + check;
						}
					} else {
						if (temp.size() == 1) {
							value = null;
							dfa[currentState][i] = null;
							;
						} else if (temp.size() > 1) {
							if (t + 1 == temp.size()) {
								if (value == "") {
									value = null;
									dfa[currentState][i] = null;
									;
								}
							}
						}

					}
				}
				dfa[currentState][i] = value;

				// check if this state exists in the dfa if not then add it
				if (value != null) {
					int x = 0;
					for (int j = 1; j < nfa.length; j++) {
						if (dfa[currentState][i].equals(dfa[j][0])) {
							x = 1;
							break;
						}
					}
					if (x == 0) {
						stateCounter++;
						dfa[stateCounter][0] = value;
					}
				}
			}
			currentState++;
		}

		// replaces the name of the states to final state name
		// String t = "";
		// int x =0;
		// boolean singleState = true;
		// for (int i = 1; i < dfa.length; i++){
		// if (dfa[i][0] != null){
		// for (int k = 0; k < dfa[i][0].length(); k++) {
		// if (dfa[i][0].charAt(k) == ',') {
		// singleState = false;
		// }
		// }
		// if (!singleState){ //if more than one state
		// for (int j = 0; j < dfa[i][0].length(); j++) {
		// //check state
		// if(dfa[i][0].charAt(j) == ',') {
		// for(int s = 0; s < st.size(); s++) {
		// if(t.equals(st.get(s))) {
		// dfa[i][0] = st.get(s);
		// x = 1;
		// break;
		// }
		// }
		// t ="";
		// }
		// else {
		// t = t+dfa[i][0].charAt(j);
		// }
		// //check last state
		// if(j+1 == dfa[i][0].length()){
		// for(int s = 0; s < st.size(); s++) {
		// if(t.equals(st.get(s))) {
		// dfa[i][0] = st.get(s);
		// x = 1;
		// break;
		// }
		// }
		// t ="";
		// }
		// if (x == 1){
		// x=0;
		// break;
		// }
		// }
		// }
		// singleState = true;
		// t = "";
		// }
		// }
		// dfa[1][0] = "1";

		// writes the header to the dfa
		for (int i = 0; i < dfa[0].length; i++) {
			dfa[0][i] = nfa[0][i];
		}

		// prints the dfa
		for (int i = 0; i < dfa.length; i++) {
			for (int j = 0; j < dfa[i].length; j++) {
				System.out.print(dfa[i][j] + "\t");
			}
			System.out.println();
		}

		// prints the final states
		System.out.print("Final states: ");
		for (int i = 0; i < st.size(); i++) {
			if (i + 1 == st.size()) {
				System.out.print(st.get(i) + ".");
			} else {
				System.out.print(st.get(i) + ", ");
			}
		}
		System.out.println();
		return dfa;
	}

	public String[][] getDFA() {
		return ret;
	}
}
